The present invention relates to methods and apparatus for protecting and authenticating information, and particularly to protecting and authenticating information using watermarks. More particularly, the present invention relates to methods and apparatus that determine whether a suspect signal is derived from a watermarked original signal by analyzing the suspect signal for the presence of a known watermark.
The growth of the Internet and networked multimedia systems has magnified the need for copyright protection of information, including image data. Copyright owners need tools for identification content authentication, that is, identification of copies of the protected work that may have been forged, filtered, or otherwise modified, as well as ownership authentication. It may also be necessary to determine a work""s chain of custody and to verify who viewed or altered the work, including when such actions occurred.
Three techniques for protecting information are encryption, authentication, and time stamps. Encryption disguises the content of information so that only users who possess the decryption xe2x80x9ckeyxe2x80x9d can convert the encrypted data back to its original form. Without the key, it is computationally infeasible to derive the original data. Another technique is authentication, which does not hide the content of the data but rather guarantees who created it. Time stamps can identify both the time at which the work was generated and the work""s owner. All three techniques may be used in various combinations.
Authentication techniques for protecting information can use what is known as a watermark. A watermark can take many forms, such as a change in the thickness of the paper on which information appears or some other physical characteristic of the medium carrying the information, or it can be included as part of the information on the medium. Typical examples are the watermarks included on checks or paper money, which aid in authenticating the item and preventing its forgery. In essence, a watermark is a code or image incorporated onto the carrier of the original information, and can be either visually perceptible or imperceptible.
A typical authentication technique using watermarks includes three parts: the watermark, the marking of the original information and the verification of the presence of the watermark in suspect information that may be copied or derived from the watermarked original information. A marking algorithm incorporates the watermark onto the image and a verification algorithm authenticates the information by determining the presence of the watermark, thereby determining both its owner and integrity. Although watermarks are traditionally associated with information such as printed items or images, they are similarly useful for other forms of information such as audio and video, including digital versions of these types of information.
Incorporating a watermark into visually perceptible information is a known method for preventing forgery and determining authenticity of data. For example, U.S. Pat. No. 5,607,188 to Bahns et al. discloses techniques for marking optical data discs with a watermark for purposes of visual identification and verification of authenticity. Similarly, U.S. Pat. No. 5,530,759 to Braudaway et al. discloses a system for placing a visible watermark on a digital image. There are reasons why it is often desirable, however, to include a watermark that is visually imperceptible, for example so that an image retains its aesthetic and commercial value or if the watermark contains information specifically intended to be invisible. U.S. Pat. No. 5,568,570 to Rabbani, U.S. Pat. No. 5,606,609 to Houser et al., and U.S. Pat. No. 5,636,292 to Rhoads are examples of patents that discuss methods and apparatus for incorporating electronic signatures or watermarks into digital data without affecting the visual quality of the information.
In addition to the increase in access to copyrighted information and ease of copying in the multimedia and Internet environments, visual information is routinely subjected to linear and nonlinear filtering, such as JPEG and MPEG compression. Accordingly, authentication techniques using watermarks to protect information effectively in these environments must withstand and survive the various transformations that information can be subjected to, such as degradation of the resolution of the signal or introduction of random errors or noise. The technique should similarly survive conversion between physical media such as through printing and optical scanning.
An effective authentication technique using watermarks should further be resistant to attempts to defeat the protection, for example by the addition of noise or another watermark to the information, or by attempts to remove the watermark from the signal. The technique should furthermore be independent of the nature of the information being protected, that is, it should apply to various types of information such as image, video, and audio signals, as well as to various formats and resolutions of the data. Thus, the technique should be able to authenticate information by detecting the presence of a known watermark in, for example, a JPEG or GIF image file as well as in an MPEG video file. For example, a watermark incorporated onto a GIF image should discernable after transformation into a JPEG image or MPEG video.
By embedding a watermark that is essentially random onto information, it is infeasible to decipher or remove the watermark without degradation of the information that is watermarked, thus providing robust protection for owners. An additional beneficial feature of a watermark based authentication technique, however, would be the ability to encode non-random information into the watermarked signal, such as time stamps, signatures, and the like, that nevertheless appears substantially random to provide robust protection for copyright owners.
According to one aspect of the present invention, a method of determining if a suspect signal is derived from a watermarked original signal is provided by the present invention. A watermark is supplied and the watermarked original signal is created by incorporating the watermark onto an original signal. At least one first watermark indicator is generated based on the watermarked original signal and the watermark. At least one second watermark indicator is generated based on the suspect signal and the watermark. Finally, a determination whether the suspect signal is derived from the watermarked original signal is made based on the at least one first and second watermark indicators. In illustrative embodiments, the original and suspect signals can be digital images, digital audio signals, or digital video signals, and the watermark is visually imperceptible after incorporation onto the original signal.
In illustrative embodiments, the watermark incorporated onto the original signal can be substantially random, for example generated based on an m-sequence. The values of the watermark can be either unipolar, for example, either zero or one, or bipolar, for example, either one or negative one. The watermark can be generated from an m-sequence having a length greater than the length of the signal onto which the watermark is incorporated, and the watermark can be generated from non-adjacent sections of the m-sequence.
In an illustrative embodiment, the original signal is a digital image that includes a plurality of planes and the watermark is incorporated onto at least one of the planes. In another embodiment a separate watermark is provided for each plane of the image. The watermark for each successive plane of the image can be generated based on a previous watermark, for example, the successive watermarks can be encrypted versions of their predecessor watermarks. In yet another embodiment the watermark can have portions that correspond to each of the planes, for example portions of the watermark can be incorporated onto one of three planes of the image based on a tripolar sequence, such as a random sequence having three values that each correspond to one of the image planes.
In another illustrative embodiment the determination of whether the suspect signal is derived from the watermarked original signal is made by determining if only a portion of the suspect signal is derived from a portion of the watermarked original signal. The first watermark indicator is based on comparing at least a portion of the watermarked original signal to a corresponding portion of the watermark, and the second watermark indicator is based on comparing at least a portion of the suspect signal to a corresponding portion of the watermark. The step of generating the first watermark indicator can include computing at least one cross-correlation value based on a portion of the watermarked original signal and a portion of the watermark and the step of generating the second watermark indicator can include computing at least one cross-correlation value based on a portion of the suspect signal and a corresponding portion of the watermark. The difference between the cross-correlation value based on the watermarked original signal and the cross-correlation value based on the suspect signal is compared to a threshold. The threshold can be based on the size of the portion of the watermarked original signal used in computing the cross-correlation value.
According to another aspect of the invention, a degree of authenticity of the suspect signal is determined based on the at least one first and second watermark indicators.
In yet another embodiment the original signal and suspect signal are arrays of pixel values and each of the arrays includes a plurality of sub-arrays. A first watermark indicator is generated by computing a plurality of cross-correlation values based on the sub-arrays of pixel values of the watermarked original signal and the watermark, and the second watermark indicator is generated by computing a plurality of cross-correlation, values based on the sub-arrays of pixel values of the suspect signal and the watermark. The determination of whether the suspect signal is derived from the watermarked original signal includes subtracting one of the second plurality of cross-correlation values from one of the first plurality of cross-correlation values and comparing the difference to a threshold. The threshold can be based on the number of values used to compute the cross-correlation values.
In still yet other embodiments the suspect signal is generated by digitizing an original suspect signal, for example by scanning a suspect image. The original signal itself can be generated based on another signal, for example by digitizing an image, video, or audio, or by filtering another digital signal. The watermark can include a first portion having a first range of values, e.g., {xe2x88x921,1}, and a second portion having a second range of values, e.g., {0,1}.
In other embodiments a watermark that exists within the original signal is derived so that the original signal is the same as the watermarked original signal. A value is provided, and locations within the original signal that represent the value are determined. The watermark existing in the original signal is derived from the determined locations. Determining if a suspect signal is derived from a watermarked original signal can include determining if the suspect signal contains a second watermark.
In yet other embodiments the generation of first and second watermark indicators includes transforming the watermarked original signal and the suspect signal into another domain, for example by using Fourier transforms, Discrete Cosine transforms or Wavelet transforms.
In other embodiments a method of determining if a second signal is derived from a first signal is provided. At least one first watermark indicator is generated based on the watermarked original signal and the watermark, and at least one second watermark indicator is generated based on the suspect signal and the watermark. Determination of whether a portion of the suspect signal is derived from a portion of the watermarked original signal is based on the at least one first and second watermark indicators. The first signal can optionally have a watermark incorporated therein. The first signal can further optionally contain a watermark derived based on information in the first signal.
In yet other embodiments an overall indicator of authenticity is computed from the first and second indicators. The overall indicator can be compared to a plurality of thresholds to indicate the authenticity of the second signal.
In still another embodiment of the present invention, an apparatus for determining if a suspect signal is derived from a watermarked original signal is provided. A first watermark indicator generator is configured to compute a first watermark indicator based on the watermarked original signal. A second watermark indicator generator is configured to compute a second watermark indicator based on the suspect signal. An authenticator is configured to determine if the suspect signal is derived from the watermarked original signal based on the first and second watermark indicators.
One feature of the present invention is that determination of whether a suspect signal is derived from the watermarked original signal is based on the suspect signal, the watermarked original signal, and the watermark, that is, without using the original signal. Therefore, the owner does not have to provide access to the original signal to permit the authentication analysis of the suspect signal.
Additional features of the invention will become apparent to those skilled in the art upon consideration of the following detailed description of the preferred embodiments exemplifying the best mode of carrying out the invention as presently perceived.